/*
 * @lc app=leetcode.cn id=68 lang=cpp
 * @lcpr version=30204
 *
 * [68] 文本左右对齐
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    vector<string> fullJustify(vector<string> &words, int maxWidth)
    {
        vector<string> result;
        int n = words.size();
        int i = 0;

        while (i < n)
        {
            int lineLength = 0; // 当前行的长度
            int start = i;      // 当前行的起始单词索引

            // 找到当前行可以容纳的单词
            // 前面的单词长度 + 当前的单词长度 + 空格长度 <= 规定的行宽就继续循环
            while (i < n && lineLength + words[i].size() + (i - start) <= maxWidth)
            {
                lineLength += words[i].size();
                i++;
            }
            // 循环结束后i为当前行的下一个单词索引

            int numWords = i - start;              // 当前行的单词数量
            int numSpaces = maxWidth - lineLength; // 当前行需要的空格数量

            string line;
            // 处理最后一行的情况：一个单词或者是最后一行
            if (numWords == 1 || i == n)
            {
                // 左对齐：单词之间用一个空格，行尾补空格
                for (int j = start; j < i; ++j)
                {
                    line += words[j];
                    if (j < i - 1)
                        line += " ";
                }
                line += string(maxWidth - line.size(), ' ');
            }
            else
            {
                // 两端对齐：均匀分布空格
                int spaceBetweenWords = numSpaces / (numWords - 1);
                int extraSpaces = numSpaces % (numWords - 1);

                for (int j = start; j < i; ++j)
                {
                    line += words[j];
                    if (j < i - 1)
                    {
                        line += string(spaceBetweenWords + (j - start < extraSpaces ? 1 : 0), ' ');
                    }
                }
            }

            result.push_back(line);
        }

        return result;
    }
};
// @lc code=end

/*
// @lcpr case=start
// ["This", "is", "an", "example", "of", "text", "justification."]\n16\n
// @lcpr case=end

// @lcpr case=start
// ["What","must","be","acknowledgment","shall","be"]\n16\n
// @lcpr case=end

// @lcpr case=start
// ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we"\n20\n
// @lcpr case=end

 */
